package org.usmile.algorithms.learn.graph.dfs;

import org.usmile.algorithms.learn.graph.AdjList;
import org.usmile.algorithms.learn.graph.Graph;

public class ConnectedComponent2 {
    public boolean isConnected(Graph graph, int v, int w) {
        if (graph == null) {
            return false;
        }

        int ccCount = 0;
        int[] visited = new int[graph.getV()];
        for (int i = 0; i < graph.getV(); i++) {
            if (visited[i] == 0) {
                ccCount++;
                dfs(graph, i, ccCount, visited);
            }
        }

        return visited[v] == visited[w];
    }

    private void dfs(Graph graph, int v, int ccId, int[] visited) {
        visited[v] = ccId;
        for (int w : graph.adj(v)) {
            if (visited[w] == 0) {
                dfs(graph, w, ccId, visited);
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new AdjList(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        System.out.println(new ConnectedComponent2().isConnected(graph, 2, 1));
    }
}
